package mo.tags.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class L763 {

    public List<Integer> partitionLabels(String s) {
        int[] count = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            count[c-'a']++;
        }
        int start = 0, end = 0, n = s.length();
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
        while (end < n) {
            char cur = s.charAt(end);
            if (count[cur -'a'] > 1) {
                count[cur-'a']--;
                map.put(cur, count[cur-'a']);
                end++;
            } else if (count[cur-'a'] == 1) {
                count[cur-'a']--;
                map.remove(cur);
                end++;
                if (map.isEmpty()) {
                    res.add(end-start);
                    start = end;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        L763 test = new L763();
        System.out.println(test.partitionLabels("eccbbbbdec"));
    }

}
